package 递归与分治算法.最大数组问题;

/**
 * @Project: Data Structure and Algorithms
 * @Package: 递归与分治算法.最大数组问题
 * @ClassName: MaxSubArrayDivideConquer
 * @Author: zhouyihe
 * @Date: 2025/11/17 21:22
 * @Description: 最大子数组-分治法
 * 把数组分成左右两半
 * 递归计算左半部分的最大子数组和
 * 递归计算右半部分的最大子数组和
 * 计算跨越中点的最大子数组和
 * 返回三者中的最大值
 * 优点:
 * 思路清晰，容易推广到类似的问题
 * 可以并行计算，提高效率
 * 缺点:
 * 时间复杂度为O(n log n)，不如动态规划
 * 需要递归调用，空间复杂度为O(log n)
 * 实现相对复杂
 */
public class MaxSubArrayDivideConquer {
    private static int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        return maxSubArrayHelper(nums, 0, nums.length - 1);
    }

    private static int maxSubArrayHelper(int[] nums, int left, int right) {
        // 基本情况
        if (left == right) {
            return nums[left];
        }

        // 分解问题
        int mid = left + (right - left) / 2;

        // 计算左半部分的最大子数组和
        int leftMax = maxSubArrayHelper(nums, left, mid);
        
        // 计算右半部分的最大子数组和
        int rightMax = maxSubArrayHelper(nums, mid + 1, right);

        // 计算跨中点的最大子数组和
        int crossMax = maxCrossingSubArray(nums, left, mid, right);

        // 返回三者中的最大值
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    private static int maxCrossingSubArray(int[] nums, int left, int mid, int right) {
        // 计算包含mid的左半部分最大和
        int leftSum = 0;
        int maxLeftSum = Integer.MIN_VALUE;

        for (int i = mid; i >= left; i--) {
            leftSum += nums[i];
            maxLeftSum = Math.max(maxLeftSum, leftSum);
        }

        // 计算包含mid+1的右半部分最大和
        int rightSum = 0;
        int maxRightSum = Integer.MIN_VALUE;

        for (int i = mid + 1; i <= right; i++) {
            rightSum += nums[i];
            maxRightSum = Math.max(maxRightSum, rightSum);
        }

        // 返回跨中点的最大子数组和
        return maxLeftSum + maxRightSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("最大子数组和: " + maxSubArray(arr)); // 输出: 6
    }


}
